<html>
<head>
<title>tree.rb</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css">
.ln { color: rgb(0,0,0); font-weight: normal; font-style: normal; }
.s0 { }
.s1 { color: rgb(0,128,0); font-weight: bold; }
.s2 { color: rgb(0,0,128); font-weight: bold; }
.s3 { color: rgb(102,0,153); font-weight: bold; }
.s4 { color: rgb(0,0,0); }
.s5 { color: rgb(0,0,255); }
.s6 { color: rgb(102,14,122); font-weight: bold; }
</style>
</head>
<BODY BGCOLOR="#ffffff">
<TABLE CELLSPACING=0 CELLPADDING=5 COLS=1 WIDTH="100%" BGCOLOR="#C0C0C0" >
<TR><TD><CENTER>
<FONT FACE="Arial, Helvetica" COLOR="#000000">
tree.rb</FONT>
</center></TD></TR></TABLE>
<pre>

<a name="l1"><span class="s0">require </span><span class="s1">&quot;rubygems&quot;</span><span class="s0"> 
<a name="l2"> 
<a name="l3"></span><span class="s2">module </span><span class="s0">Db 
<a name="l4">  </span><span class="s2">module </span><span class="s0">Core 
<a name="l5">    </span><span class="s2">class </span><span class="s0">Database 
<a name="l6"> 
<a name="l7">      attr_accessor </span><span class="s3">:datas</span><span class="s4">, </span><span class="s3">:parent_node</span><span class="s4">, </span><span class="s3">:pre_node</span><span class="s4">, </span><span class="s3">:next_node</span><span class="s4">, </span><span class="s3">:structure</span><span class="s0"> 
<a name="l8"> 
<a name="l9">      </span><span class="s2">def </span><span class="s0">initialize(structure=</span><span class="s5">3</span><span class="s0">) 
<a name="l10">        </span><span class="s6">@structure </span><span class="s0">= structure 
<a name="l11">        </span><span class="s6">@datas </span><span class="s0">= [] 
<a name="l12">        </span><span class="s6">@parent_node </span><span class="s0">= </span><span class="s1">&quot;sample&quot;</span><span class="s0"> 
<a name="l13">        </span><span class="s6">@pre_node </span><span class="s0">= </span><span class="s2">nil</span><span class="s0"> 
<a name="l14">        </span><span class="s6">@leaf_node </span><span class="s0">= </span><span class="s2">nil</span><span class="s0"> 
<a name="l15">      </span><span class="s2">end</span><span class="s0"> 
<a name="l16"> 
<a name="l17">      </span><span class="s2">def </span><span class="s0">keys 
<a name="l18">        id = [] 
<a name="l19">        </span><span class="s6">@datas</span><span class="s0">.each {|k| id &lt;&lt; k[</span><span class="s5">0</span><span class="s0">]} 
<a name="l20">        </span><span class="s2">return </span><span class="s0">id 
<a name="l21">      </span><span class="s2">end</span><span class="s0"> 
<a name="l22"> 
<a name="l23">      </span><span class="s2">def </span><span class="s0">insert(key</span><span class="s4">, </span><span class="s0">value) 
<a name="l24">        inserting_element = key 
<a name="l25">        _datas = [] &lt;&lt; inserting_element &lt;&lt; value 
<a name="l26">        </span><span class="s6">@datas </span><span class="s0">&lt;&lt; _datas 
<a name="l27">        sort_keys 
<a name="l28">        divide </span><span class="s2">if </span><span class="s6">@datas</span><span class="s0">.length &gt; </span><span class="s3">:structure</span><span class="s0"> 
<a name="l29">      </span><span class="s2">end</span><span class="s0"> 
<a name="l30"> 
<a name="l31"> 
<a name="l32">    private 
<a name="l33">      </span><span class="s2">def </span><span class="s0">sort_keys 
<a name="l34">        </span><span class="s2">self</span><span class="s0">.datas.sort {|a</span><span class="s4">, </span><span class="s0">b| a[</span><span class="s5">0</span><span class="s0">]&lt;=&gt;b[</span><span class="s5">0</span><span class="s0">]} 
<a name="l35">      </span><span class="s2">end</span><span class="s0"> 
<a name="l36"> 
<a name="l37">      </span><span class="s2">def </span><span class="s0">divide 
<a name="l38">          no_of_divides = (</span><span class="s6">@datas</span><span class="s0">.length/</span><span class="s6">@structure</span><span class="s0">).ceil 
<a name="l39">          leaf_items = </span><span class="s6">@datas</span><span class="s0">.values_at(</span><span class="s5">0</span><span class="s0">..no_of_divides-</span><span class="s5">1</span><span class="s0">) 
<a name="l40">          </span><span class="s6">@datas</span><span class="s0">.slice!(</span><span class="s5">0</span><span class="s4">, </span><span class="s6">@structure</span><span class="s0">) 
<a name="l41">          new_node = Leaf.new() 
<a name="l42">          new_node.datas = leaf_items 
<a name="l43">          new_node.pre_node = </span><span class="s6">@pre_node</span><span class="s0"> 
<a name="l44">          new_node.next_node = </span><span class="s2">self</span><span class="s0"> 
<a name="l45">          new_node.pre_node.next_node = new_node </span><span class="s2">unless </span><span class="s0">new_node.pre_node = nil? 
<a name="l46"> 
<a name="l47">      </span><span class="s2">end</span><span class="s0"> 
<a name="l48"> 
<a name="l49"> 
<a name="l50">    </span><span class="s2">end</span><span class="s0"> 
<a name="l51">  </span><span class="s2">end</span><span class="s0"> 
<a name="l52"></span><span class="s2">end</span><span class="s0"> 
<a name="l53"> 
<a name="l54"> 
<a name="l55">a = Db::Core::Database.new 
<a name="l56">a.insert(</span><span class="s5">1</span><span class="s4">, </span><span class="s5">2</span><span class="s0">) 
<a name="l57"></span></pre>
</body>
</html>